public class Solution2 {
    //213. 打家劫舍 II
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0],nums[1]);
        }
        int counnt1 = nums[0] + rob1(nums,2,n-2);
        int counnt2 = rob1(nums,1,n-1);
        return Math.max(counnt1,counnt2);
    }
    public int rob1(int[] nums,int l,int r) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[l] = nums[l];
        for (int i = l+1; i <= r; i++) {
            f[i] = g[i-1] +  nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }

        return Math.max(f[r],g[r]);
    }
}
